\subsection{Fourier Transformation}
%\textbf{THIS IS GOLD!!!! Here is a good link that could be used as an introduction (who was Fourier), as well as using the images to see how a sum of sinusoids can describe virtually all signals. Scroll down and look at pictures; maybe we can use them. More specifically, I think this is a good sentence to use: "There is no difference between the signal in (a) and the sum of the signals in (b), just as there is no difference between 7 and 3+4.":  http://www.dspguide.com/ch8/1.htm - Gustav, 25 May}

%\textbf{Also, use this website for FFT: http://www.dspguide.com/ch12.htm - Gustav, 25 May}

In this section the basic Fourier transform, the DTFT (Discrete-Time Fourier Transformation), is explained. Other variants, such as the FFT (Fast Fourier Transform), are not explained in this report as these are just variants or optimized algorithms that achieve basically the same thing. The project will use the FFT because this is better optimized, but to understand Fourier transformation, understanding of the DTFT is needed.

A transformation is basically mapping a set of data from one format to another, in this case the fourier transformation maps the data between the time domain and the frequency domain.

The purpose of the DTFT is to map between the time domain and the frequency domain given a certain window of samples of a signal. Said in a different way, the DTFT takes a complete signal and breaks it down into each of its components, or ingredients, metaphorically much like breaking a smoothie down into every ingredient used to know how to make an identical smoothie. The inverse DTFT does the exact opposite; it blends the ingredients and makes a smoothie.

The formula for the Fourier transformation is as follows:

\begin{align}
X_{k} = \frac{1}{N} \sum_{n = 0}^{N - 1} x_{n} * e^{-i 2 \pi k n/N}
\end{align}

And the Inverse Fourier transformation is as follows:

\begin{align}
x_{n} = \sum_{n = 0}^{N - 1} X_{k} * e^{i 2 \pi k n/N}
\end{align}

Where:

$N$ = number of samples.

$n$ = the current sample, going from $0$ to $N-1$.

$x_{n}$ = value of the signal at time $n$.

$k$ = the frequency considered, going from $0 Hz$ to $N-1 Hz$.

$X_{k}$ = the amount of frequency $K$ in the signal (Amplitude and phase, is a complex number).

$n/N$ is the percent of time one have gone through.

$2 * \pi * k$ = speed in radians/seconds.

$e^{-ix}$ is the backwards-moving circular path.

The last two combined is backwards movement in a circle with speed radians/second.

$e^{-i2 * \pi * k}$

Each sample in the sample window is read. $n/N$ indicates in percentage how far through the sample window the transformation is for a certain frequency. In other words, if the sample window is 1 second long and the sample size $N = 10$, then $n/N$ checks the position on the circle at $0.1$ second intervals $N$ times.

$e^{-i2 * \pi * k n/N}$

By using $\frac{1}{N}$ in the forward Fourier transform the actual size of the time spikes are given. It is worth noting that $\frac{1}{N}$ can be placed in the inverse Fourier transformation as well. This will normalize the signal when transformed into time domain. When having to build a complete frequency domain of a signal, several frequencies have to be considered, or more precisely, the frequencies from $0 Hz$ to $N-1 Hz$ have to be considered. So the higher amount of samples, the higher amount of frequencies need to be calculated between time- and frequency-domain, and vice versa.

The report will not look into the inverse Fourier transform as the project will only need to convert from time domain to frequency domain.

So if one takes a look at the Fourier transformation it can be seen that with a bit of moving things around the formula can be made a bit easier to understand.

$X_{k} = \frac{1}{N} \sum_{n = 0}^{N - 1} x_{n} * e^{-i 2 \pi (n/N) k}$

This gives the opportunity to split the $e^{-i 2 \pi (n/N) k}$ part up in three different parts, all which serve a different purpose, $2 \pi$ which is one full rotation on a circle, $(n/N)$ which gives a percentage, defining how far around the circle one is, and lastly $k$ which is the frequency that acts like a multiplier. 

Given a signal that looks like figure \ref{fig:fourierexample}

\begin{figure}[htbp]
\centering
\includegraphics[width=0.7\textwidth]{images/TheoryDesign/fouriersignal.png}
\caption{A signal with four samples, illustrated by orange dots.}
\label{fig:fourierexample}
\end{figure}

This is a signal in the time domain which has been sampled four times, represented by the orange dots. This can be reverted into a frequency domain. First the variables are filled in. This has to be done for each of the frequencies between, and including, 0 Hz and 3 Hz, since there are four time samples. Take the example where $k$ is equal to 0 Hz.

There are four samples, so $N = 4$ and for each of these samples the value is as follows $X_{n} = \begin{bmatrix} 5 & 0 & -1 & 0 \end{bmatrix}$. As $\sum_{n = 0}^{N - 1}$ is the sum of everything that follows it, it can be written as four equations instead, so that each sample looks like the following:

$X_{0-sample0} = 5 * e^{-i 2 \pi (0/4) 0} = 5$

$X_{0-sample1} = 0 * e^{-i 2 \pi (1/4) 0} = 0$

$X_{0-sample2} = -1 * e^{-i 2 \pi (2/4) 0} = -1$

$X_{0-sample3} = 0 * e^{-i 2 \pi (3/4) 0} = 0$ 

Now all the equations have been calculated individually and just needs to be summed up and normalized;

$X_{0} = \frac{1}{N}(X_{0-sample0} + X_{0-sample1} + X_{0-sample2} + X_{0-sample3}) = \frac{1}{4}(5 + 0 + (-1) + 0) = 1$

What was just done here it the exact same thing as $X_{k} = \frac{1}{N} \sum_{n = 0}^{N - 1} X_{n} * e^{-i 2 \pi (n/N) k}$.

When doing the same with each of the other frequencies, the end results of this signal is the following for $X_{k}$:

$X_{0} = 1$

$X_{1} = 1.5$

$X_{2} = 1$

$X_{3} = 1.5$

These values are complex numbers where the magnitude of each frequency is the real part of the number. In this case, the imaginary part is zero and therefore no calculation has to be done on the numbers. 

The results can then be summed up and figure \ref{fig:fourierfrequency} shows how a simplified frequency domain with the four frequencies look.

\begin{figure}[htbp]
\centering
\includegraphics[width=0.7\textwidth]{images/TheoryDesign/fourierfrequency.png}
\caption{The four frequencies and their magnitude.}
\label{fig:fourierfrequency}
\end{figure}